/**
 * https://leetcode.cn/problems/longest-path-with-different-adjacent-characters/submissions/584260019/
 * 2246. 相邻字符不同的最长路径
 * difficulty 陈贝纯 2024.12.01
 * 换根dp
 */

class Solution {
public:
    int ans=0;
    int dfs(int y,vector<vector<int>>& adj,string& s){
        int maxlen=0;
        for(auto &x:adj[y]){
            int len=dfs(x,adj,s)+1;
            if(s[x]!=s[y]){
                ans=max(ans,maxlen+len);
                maxlen=max(maxlen,len);
            }
        }
        return maxlen;
    }
    int longestPath(vector<int>& parent, string s) {
        int n=s.size();
        vector<vector<int>> adj(n);
        for(int i=1;i<parent.size();++i)
        adj[parent[i]].push_back(i);
        dfs(0,adj,s);
        return ans+1;
    }
};